1. Field of the Invention
The present invention relates to pseudorandom number generators and, in particular, to pseudorandom number generators which are suitable for so-called stream ciphers, that is sequential encrypting devices. In particular, the inventive pseudorandom number generators are suitable as key sequence generators for such ciphering devices.
2. Description of the Related Art
Such a well-known random number generator is illustrated in FIG. 12. The pseudorandom number generator of FIG. 12 which is also referred to as a linear feedback shift register, includes a plurality of memory cells 51, 52, 53, 54, which, in FIG. 12, are numbered 0 to n. The memory cells can be initialized to an initial value via initializing means 55. The memory cells 51 to 54 together form feedforward means, while the linear shift register formed by the memory cells 51 to 54, is fed back by feedback means coupled between an output 56 of the circuit and the memory cell n. In particular, the feedback means includes one or several combining means 57, 58 which are fed by respective feedback branches 59a, 59b, 59c as is exemplarily illustrated in FIG. 12. The initial value of the last combining means 58 is fed into the memory cell n which, in FIG. 12, is designated by 54.
The linear feedback shift register shown in FIG. 12 is driven by a clock so that the occupancy of the memory cells is shifted by one step, referring to FIG. 12, to the left in each clock cycle, so that in each clock cycle the state stored in the memory means 51 is output as a number, while at the same time the value is fed into the first memory cell n of the sequence of memory cells at the output of the last combining means 58. The linear feedback shift register illustrated in FIG. 12 thus provides a sequence of numbers responsive to a sequence of clock cycles. The sequence of numbers obtained at the output 56 depends on the initial state made by the initializing means 55 before operating the shift register. The initial value input by the initializing means 55 is also referred to as a seed, which is why such arrangements illustrated in FIG. 12 are also referred to as seed generators.
The sequence of numbers obtained at the output 56 is referred to as a pseudorandom sequence of numbers since the numbers seem to follow one another in a seemingly random way, but are periodical in all even though the period duration is great. In addition, the sequence of numbers can be repeated unambiguously and thus has a pseudorandom character when the initializing value fed to the memory cells by the initializing means 55 is known. Such shift registers are, for example, employed as key stream generators to provide a stream of encoding/decoding keys depending on a special initializing value (seed).
Such shift registers illustrated in FIG. 12 have the disadvantage of a small linear complexity. Thus, 2 n bits of the output sequence are sufficient in an n-bit LFSR (LFSR=linear feedback shift register) to calculate the entire sequence. The advantage of such well-known LFSRs illustrated in FIG. 12, however, is that they incur very low hardware costs.
In addition, there are irregularly clocked LFSRs. They incur somewhat increased hardware costs with a mostly smaller period. The linear complexity, however, may be increased considerably. A disadvantage of such irregularly clocked devices, however, is the fact that the output sequence can, in principle, be established by means of measuring the current in an SPA (SPA=simple power analysis) due to the irregular clocking. By using the shift register devices as parts of key generators which produce data to be kept secret inherently, that is key data, it is of crucial importance for them to be safe against any kind of cryptographic attacks.
On the other hand, there is the requirement in such devices, in particular when they are to be accommodated on chip cards, that the hardware costs be low. Put differently, the chip area such devices occupy must be as small as possible. The reason for this is that in semiconductor manufacturing, the chip area of an entire device in the end determines the price and thus the profit margin of the chip manufacturer. In addition, a specification, especially in chip cards, usually is such that a customer sets the maximal area of a processor chip, in square millimeters, on which different functionalities must be accommodated. It is thus the task of the circuit manufacturer to distribute this valuable area for the individual components. Regarding cryptographic algorithms which are becoming more complex all the time, efforts of the chip manufacturer are directed to the chip having the largest amount of memory possible to be able to calculate even algorithms requiring lots of working memory in an acceptable time. The chip area for key generators and other such components thus must be kept as small as possible in order to be able to accommodate a greater amount of memory on the chip area given.
The general requirement for key generators or devices for generating a pseudorandom sequence of numbers thus is to be safe on the one hand and to require as little space as possible on the other hand, that is to incur the lowest possible hardware costs.
In principle, linear shift registers have different applications in coding theory, cryptography and other areas in electro-technology. The output sequences of linear shift registers have useful structural features which can be divided into algebraic features and distribution features.
One knows that the output sequence of an n-step linear shift register, as has been explained, is periodic. The length of the period can be rather large and is often exponential with regard to n, that is the number of memory cells. In particular, the length of the period is 2n−1 when the shift register is based on a primitive feedback polynomial.
The linear complexity of such a sequence, however, at most equals n. The linear complexity of a periodic sequence, as per definition, equals the number of cells of the smallest possible shift register the sequence considered can produce.
Due to this fact, it can be shown that, as has been explained, 2 n successive expressions of the sequence are sufficient to predict all the remaining expressions of the sequence. Additionally, there is an efficient algorithm, the so-called Berlekamp Massey algorithm, for calculating the parameters required to obtain the entire sequence. For this reason, sequences of linear shift registers, despite their potentially great periods and their statistically good distribution features, are not directly suitable as key sequences in so-called stream ciphers. In addition, there are other applications in which the comparatively small linear complexity of a sequence produced by a linear shift register is to be seen as a disadvantage.
Conventionally, linear shift registers are described by their characteristic polynomial. The degree of the characteristic polynomial equals the number of delay elements, which are usually embodied as flip-flops, of the shift register considered. The exponents of the terms of f(x), except for the leading term, correspond to the delay elements of the shift register contributing to the feedback. The linear shift register illustrated in FIG. 12 would thus have a characteristic polynomial of the following kind:f(x)=xn+1+xn+ . . . +x+1.
If such linear shift registers, as are exemplarily illustrated in FIG. 12, are loaded with an initializing state by the initializing means 55, wherein this state is also referred to as the initial state vector, they will typically output a periodic sequence which, depending on the implementation, has a certain pre-period and a subsequent period. Linear shift registers will always be periodic. It is strived for in technological applications for the output sequence to have both a great period length and a high linear complexity.
In principle, pseudorandom number generators, as have, for example, been illustrated referring to FIG. 12, are required for different purposes, that is for simulation purposes, for performing random samples in statistic applications, for testing computer programs, for sequentially ciphering to generate a key sequence, for probabilistic algorithms, in numerical mathematics, in particular for a numerical integration, for generating keys in cryptology or for Monte Carlo methods. In particular, pseudorandom number generators are commercially employed for safety ICs, within typically integrated random number generators, within crypto-modules or for pay TV applications or even in chip cards for cell phones, etc.
Basically, random numbers can be generated on the basis of a physically random process or else by certain mathematical manipulations. Only in the latter case, we speak of pseudorandom numbers, while in the first case, we speak of true random numbers. In a pseudorandom number generator, numbers are generated from certain initial values, the so-called seed which is effected by the initializing means 55 of FIG. 12, typically at a very high speed, wherein the numbers must pass a number of tests which true random numbers would also pass. The seed, however, is produced by a true physical random process. As has been illustrated referring to FIG. 12, linear feedback shift registers (LFSR) are used to provide pseudorandom number generators. Shift registers with a linear feedback are of advantage in that they are mathematical theories stating that certain features of the pseudorandom numbers produced can be predicted theoretically. The most important features are the period length and the linear complexity of the output sequence. Thus, there are theories for linear shift registers which make it possible to either exactly predict the output sequence or at least to make statements on the minimum length of the period and the maximum size of the linear complexity. Put differently, lower thresholds for the period length and the linear complexity can be indicated and proved by mathematical processes.
The disadvantage connected to using shift registers with linear feedback as basic building blocks in pseudorandom number generators is that the output sequences have a linear complexity which is relatively small compared to the period length. The reason for this is that the output sequences of an individual shift register with linear feedback already have such a disproportion of period length to linear complexity. When a shift register with linear feedback, for example, includes N memory cells, such as, for example, flip-flops, the period length of the output sequence can at most take the value 2N−1. If the feedback polynomial is selected well, this will really be the case. The linear complexity of the output sequence, however, at most equals N.
In order to increase the period length and at the same time the linear complexity, it would thus be necessary using a shift register with linear feedback to keep on increasing the number of memory cells, which, on the one hand, entails problems regarding the space and which, on the other hand, entails electrical problems since all the memory cells in a shift register must be addressed by a block, wherein synchronization problems are becoming ever more pronounced when the number of memory cells increases.
Additionally, an ever greater number of memory cells within a single shift register has the result that the pseudorandom number generator can be localized ever more easily by an attacker and thus becomes the target of a crypto attack ever more easily. This is of special disadvantage when the pseudorandom number generator contains secret information or operates on the basis of secret information, which will typically be the case when the pseudorandom number generator is used in a cryptographic field.
Such pseudorandom number generators described herein before are usually used in stream ciphers, which are, for example, employed in safety ICs, random number generators, crypto modules, pay TV applications, cell phones or chip cards.
In principle, the requirements in pseudorandom number generators differ depending on the field in which the pseudorandom number generators are employed. If a pseudorandom number generator is, for example, required to control a simulation based on random numbers, such as, for example, a Monte Carlo simulation, certain randomness will be required from the pseudorandom numbers in order for the simulation to operate optimally. Safety aspects, however, do not play a role. If, however, a pseudorandom number generator is to be employed in a stream cipher, it will have to deal with processing secret information. Typically, the initialization of the random number generator, that is the so-called seed, will be the secret or the session key which must be known to both a sender of encrypted data as well as to a receiver of the encrypted data to perform encryption on the sender side and to perform decryption on the receiver side.
In contrast to plain pseudorandom number generators, additional requirements are placed on key sequence generators in a stream cipher. It is thus not sufficient for optimal applications for the key sequence to have good statistical features (which, for a Monte Carlo simulation, will be sufficient), but the output sequence or key sequence the pseudorandom number generator provides must not make possible drawing conclusions to the current state of the key sequence generator itself and, in particular, to the initialization, which is the actual secret, which is the basis for the key sequence. Put differently, so-called correlation immunity is required for a pseudorandom number generator which is to be employed in a stream cipher.
Complete correlation immunity means that the output sequence (=key sequence) does not contain any information on the one or several individual input sequences (which here are the preferably used individual shift register sequences). The output sequence must be uncorrelated to each individual shift register sequence (input sequence).
Additionally, high-quality stream ciphers have the characteristic of having the so-called “strict avalanche criterion”. The following is meant by this criterion. A bit of the output sequence (key sequence) always has to change with the probability of 0.5 when exactly one input bit is complemented, i.e. when a 1 becomes a 0 or when a 0 becomes a 1, while the other input bits, however, remained unchanged. From that point of view it is not important which input bit will be complemented.
Both the correlation immunity and the strict avalanche criterion are thus quality requirements which, in the end, determine whether a pseudorandom number generator will not only be used for statistical simulations but also for cryptographic purposes, since ever higher safety requirements of the pseudorandom number generators can be fulfilled with an ever improving correlation immunity and/or avalanche criterion.